package com.chao.stucture.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author : Rookie
 * @description : 构建堆，插入或者删除元素
 * @date : 2023/7/9
 */
public class Heap {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(10);
        list.add(3);
        list.add(5);
        list.add(1);
        buildMaxRootHeap(list);
        System.out.println("大根堆：" + list);
        list.add(6);
        buildMaxRootHeap(list);
        System.out.println("添加一个元素，重新构建的大根堆：" + list);
        list.remove(Integer.valueOf(6));
        buildMaxRootHeap(list);
        System.out.println("删除一个元素，重新构建的大根堆：" + list);
    }

    private static void buildMaxRootHeap(List<Integer> list) {
        int n = list.size();
        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapIfy(list,i);
        }
    }

    private static void maxHeapIfy(List<Integer> list,int i) {
        int size = list.size();
        int left = getLeftSonIndex(i);
        int right = getRightSonIndex(i);
        int maxIndex = i;

        if (left < size && list.get(left) > list.get(maxIndex)) {
            maxIndex = left;
        }

        if (right < size && list.get(right) > list.get(maxIndex)) {
            maxIndex = right;
        }


        if (maxIndex != i) {
            swap(list,maxIndex,i);
            maxHeapIfy(list,maxIndex);
        }
    }

    private static int getLeftSonIndex(int i) {
        return 2*i+1;
    }

    private static int getRightSonIndex(int i) {
        return 2*i+2;
    }

    private static void swap(List<Integer> list,int i,int j) {
        Integer temp = list.get(i);
        list.set(i,list.get(j));
        list.set(j,temp);
    }
}
